package com.banmao.CarlCamp.Day04;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 */
@Slf4j
public class LC24 {

    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        Stack<ListNode> stack = new Stack<>();
        stack.push(dummyHead);
        ListNode cur = head;
        while (cur != null || !stack.isEmpty()) {
            if (stack.size() > 2) {
                ListNode n2 = stack.pop();
                ListNode n1 = stack.pop();
                ListNode pre = stack.pop();
                n2.next = n1;
                n1.next = cur;
                pre.next = n2;
                stack.push(n1);
            }
            if (cur != null) {
                stack.push(cur);
                cur = cur.next;
            } else {
                stack.clear();
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        LC24 lc24 = new LC24();
        node = lc24.swapPairs(node);
        log.info("{}", node);
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}
